﻿#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<string>
#include<math.h>


//Fibonacci数列
//https://www.nowcoder.com/questionTerminal/18ecd0ecf5ef4fe9ba3f17f8d00d2d66
//暴力方法 vector
//int main()
//{
//    int n = 0;
//    cin >> n;
//    vector<int> v;
//    if (n >= 1)
//    {
//        v.push_back(0);
//        v.push_back(1);
//    }
//    int num = 0, i = 2;
//    while (1)
//    {
//        v.push_back(v[i - 2] + v[i - 1]);
//        if (v[i++] > n) { break; }
//    }
//    int min = v[i - 1];
//    for (int j = 0; j < i; ++j)
//    {
//        if (abs(v[j] - n) < min) { min = abs(v[j] - n); }
//    }
//    cout << min << endl;
//}

//优化一 - 空间复杂度O(1)
//int main()
//{
//    int n = 0;
//    cin >> n;
//    int num1 = 0, num2 = 1, num3 = 0, min = n;
//    while (num3 < n)
//    {
//        num3 = num1 + num2;
//        if (abs(num3 - n) < min) { min = abs(num3 - n); }
//        num1 = num2;
//        num2 = num3;
//    }
//    cout << min << endl;
//}

//优化二 - 减少变量数
//int main()
//{
//    int n = 0;
//    cin >> n;
//    int num1 = 0, num2 = 1;
//    while (num2 < n)
//    {
//        int tmp = num1 + num2;
//        num1 = num2;
//        num2 = tmp;
//    }
//    cout << (abs(num1 - n) < abs(num2 - n) ? abs(num1 - n) : abs(num2 - n)) << endl;
//}



//合法括号序列判断
//https://www.nowcoder.com/questionTerminal/d8acfa0619814b2d98f12c071aef20d4?pos=11&mutiTagIds=609&orderByHotValue=1&questionTypes=000100
//class Parenthesis {
//public:
//    bool chkParenthesis(string A, int n)
//    {
//        int num = 0;
//        for (const auto& s : A)
//        {
//            if (s == '(') { ++num; }
//            else if (s == ')') { --num; }
//            else { return false; }
//        }
//        if (num == 0) { return true; }
//        return false;
//    }
//};